Kevin Mader
14 April 2016
ETHZ: 227-0966-00L
Voronoi Tesselations
Self-Avoiding / Nearest Neighbor
Alignment / Distribution Tensor
Two point correlation
We examine a number of different metrics in this lecture and additionally to classifying them as Local and Global we can define them as point and voxel-based operations.
| x | y | z |
|---|---|---|
| 0 | 1 | 1 |
| 3 | 1 | 1 |
| 1 | 1 | 0 |
| 1 | 1 | 2 |
Going back to our original cell image
We can characterize the sample and the average and standard deviations of volume, orientation, surface area, and other metrics
With all of these images, the first step is always to understand exactly what we are trying to learn from our images.
We want to know how many cells are alive
We want to know where the cells are alive or most densely packed
A tool which could be adapted to answering a large variety of problems
With most imaging techniques and sample types, the task of measurement itself impacts the sample.
\[ \downarrow \]
| x | y | vx | vy |
|---|---|---|---|
| 20.19 | 10.69 | -0.95 | -0.30 |
| 20.19 | 10.69 | 0.30 | -0.95 |
| 293.08 | 13.18 | -0.50 | 0.86 |
| 293.08 | 13.18 | -0.86 | -0.50 |
| 243.81 | 14.23 | 0.68 | 0.74 |
| 243.81 | 14.23 | -0.74 | 0.68 |
\[ \cdots \]
So if we want to know the the mean or standard deviations of the position or orientations we can analyze them easily.
| Min. | 1st Qu. | Median | Mean | 3rd Qu. | Max. | |
|---|---|---|---|---|---|---|
| x | 6.90 | 215.70 | 280.50 | 258.20 | 339.00 | 406.50 |
| y | 10.69 | 111.60 | 221.00 | 208.60 | 312.50 | 395.20 |
| Length | 1.06 | 1.57 | 1.95 | 2.08 | 2.41 | 4.33 |
| vx | -1.00 | -0.94 | -0.70 | -0.42 | 0.07 | 0.71 |
| vy | -1.00 | -0.70 | 0.02 | 0.04 | 0.71 | 1.00 |
| Theta | -180.00 | -134.10 | -0.50 | -4.67 | 130.60 | 177.70 |
When given a group of data, it is common to take a mean value since this is easy. The mean bone thickness is 0.3mm. This is particularly relevant for groups with many samples because the mean is much smaller than all of the individual points.
One of the first metrics to examine with distribution is density \( \rightarrow \) how many objects in a given region or volume.
It is deceptively easy to calculate involving the ratio of the number of objects divided by the volume.
It doesn't tell us much, many very different systems with the same density and what if we want the density of a single point? Does that even make sense?
Oxford American \( \rightarrow \) be situated next to or very near to (another)
Given a set of objects with centroids at \[ \textbf{P}=\begin{bmatrix} \vec{x}_0,\vec{x}_1,\cdots,\vec{x}_i \end{bmatrix} \]
We can define the nearest neighbor as the position of the object in our set which is closest
\[ \vec{\textrm{NN}}(\vec{y}) = \textrm{argmin}(||\vec{y}-\vec{x}|| \forall \vec{x} \in \textbf{P}-\vec{y}) \]
We define the distance as the Euclidean distance from the current point to that point, and the angle as the
\[ \textrm{NND}(\vec{y}) = \textrm{min}(||\vec{y}-\vec{x}|| \forall \vec{x} \in \textbf{P}-\vec{y}) \] \[ \textrm{NN}\theta(\vec{y}) = \tan^{-1}\frac{(\vec{\textrm{NN}}-\vec{y})\cdot \vec{j}}{(\vec{\textrm{NN}}-\vec{y})\cdot \vec{i}} \]
So examining a simple starting system like a grid, we already start running into issues.
We thus add an additional clause (only relevant for simulated data) where if there are multiple equidistant neighbors, a nearest is chosen randomly
This ensures when we examine the orientation distribution (NN\( \theta \)) of the neighbors it is evenly distributed
For the rest of these sections we will repeatedly use several simple in-silico systems to test our methods and try to better understand the kind of results we obtain from them.
Compression
\[ \begin{bmatrix} x^\prime \\ y^\prime \end{bmatrix} = \alpha \begin{bmatrix} x \\ y \end{bmatrix} \]
Shearing
\[ \begin{bmatrix} x^\prime \\ y^\prime \end{bmatrix} = \begin{bmatrix} 1 & \alpha \\ 0 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} \]
\[ \begin{bmatrix} x^\prime \\ y^\prime \end{bmatrix} = \begin{bmatrix} \textrm{sign}(x) \left(\frac{|x|}{m}\right)^\alpha m \\ \textrm{sign}(y) \left(\frac{|y|}{m}\right)^\alpha m \end{bmatrix} \]
\[ \theta (x,y) = \alpha \sqrt{x^2+y^2} \]
\[ \begin{bmatrix} x^\prime \\ y^\prime \end{bmatrix} = \begin{bmatrix} \cos\theta(x,y) & -\sin\theta(x,y) \\ \sin\theta(x,y) & \cos\theta(x,y) \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} \]
We notice there are several fairly significant short-comings of these metrics (particularly with in-silico systems)
Luckily we are not the first people to address this issue
Using a uniform grid of points as a starting point has a strong influence on the results. A better approach is to use a randomly distributed series of points
Voronoi tesselation is a method for partitioning a space based on points. The basic idea is that each point \( \vec{p} \) is assigned a region \( \textbf{R} \) consisting of points which are closer to \( \vec{p} \) than any of the other points. Below the diagram is shown in a dashed line for the points shown as small circles.